#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    int ans1(vector<int>& nums){
        int len = nums.size();
        vector<int> dp(len, 0);

        for(int i = 0; i != len; i++){
            dp[i] = 1;
            for(int j = 0; j != i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }

        int max_len = *max_element(dp.begin(), dp.end());
        return max_len;
    }
};

void test1(){
    Solution s;
    vector<int> nums = {10,9,2,5,3,7,101,18};

    int ret = s.ans1(nums);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {1,3,6,7,9,4,10,5,6};

    int ret = s.ans1(nums);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();

    return 0;
}